package Lee_code;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;

public class Lee_417 {
    int row, column;
    boolean Pac, Atl;
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        row = heights.length;
        column = heights[0].length;
        List<List<Integer>> res = new LinkedList<>();

        for(int i=0; i<row; i++)
        {
            for(int j=0; j<column; j++)
            {
                boolean[][] seen = new boolean[row][column];
                Pac = false;
                Atl = false;
                dfs(i, j, seen, heights);
                if(Pac && Atl)
                {
                    List<Integer> temp = new LinkedList<>();
                    temp.add(i);
                    temp.add(j);
                    res.add(temp);
                }
            }
        }
        return res;

    }

    private void dfs(int i, int j, boolean[][] seen, int[][] heights) {
        if(i<0||i>=row||j<0||j>=column||seen[i][j])
        {
            return;
        }

        if(i==0||j==0)
            Pac = true;
        if(i==row-1||j==column-1)
            Atl = true;
        //上下左右四个方向

        seen[i][j] = true;

        if( i+1<row && heights[i][j]>=heights[i+1][j])
        {
            dfs(i+1, j, seen, heights);
        }

        if( i-1>=0 && heights[i][j]>=heights[i-1][j])
        {
            dfs(i-1, j, seen, heights);
        }

        if(j+1<column && heights[i][j]>=heights[i][j+1])
        {
            dfs(i, j+1, seen, heights);
        }

        if(j-1>=0 && heights[i][j]>=heights[i][j-1])
        {
            dfs(i, j-1, seen, heights);
        }
    }
}
